package com.sakura.链表;

public class Code106_链表相交 {


    private class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1 先统计两个链表的长度
        int lenA = 0, lenB = 0;
        for (ListNode cur = headA; cur != null; cur = cur.next) {
            lenA++;
        }
        for (ListNode cur = headB; cur != null; cur = cur.next) {
            lenB++;
        }
        if (lenA < lenB) {
            // 2 移动指针，让两个链表长度相同
            int i = lenB - lenA;
            while (i-- > 0) {
                headB = headB.next;
            }
        } else if (lenA > lenB) {
            int i = lenA - lenB;
            while (i-- > 0) {
                headA = headA.next;
            }
        }
        ListNode p1 = headA, p2 = headB;
        while (p1 != null) {
            if (p1 == p2) {
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
}
